/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package ads.similar;

import java.util.ArrayList;
import java.util.PriorityQueue;

/**
 *
 * @author frama_000
 */
public class SimilarWords {

    public static ArrayList<Word> findSimilarWords(ArrayList<String> words, String searched, int responseSize) {
        PriorityQueue<Word> pq = new PriorityQueue<>(words.size(), new WordComperator());

//        long t1, t2, z1, z2, az = 0;
//        int counter = 0;
//        System.out.println("Creating prioqueue...");
//        t1 = System.currentTimeMillis();
        for (String w : words) {
//            z1 = System.currentTimeMillis();
            pq.add(new Word(w, levenshteinDistance(searched, w)));
//            z2 = System.currentTimeMillis();
//            az += z2 - z1;
//            System.out.println("Avarage levenshtein time: " + az / Math.pow(counter, 1));
//            counter++;
        }
//        t2 = System.currentTimeMillis();
//        System.out.println("Prioqueue finished in " + (t2 - t1) + " Milliseconds");

        ArrayList<Word> bestMatches = new ArrayList<>();
        for (int i = 0; i < responseSize; i++) {
            bestMatches.add(pq.poll());
        }
        return bestMatches;
    }

    public static int levenshteinDistance(String w1, String w2) {

        int[][] matrix = new int[w1.length()][w2.length()];

        for (int i = 0; i < w1.length(); i++) {
            matrix[i][0] = i;
        }
        for (int i = 0; i < w2.length(); i++) {
            matrix[0][i] = i;
        }

        for (int i = 1; i < w1.length(); i++) {
            for (int j = 1; j < w2.length(); j++) {
                if (w1.charAt(i) == w2.charAt(j)) {
                    matrix[i][j] = matrix[i - 1][j - 1];
                } else {
                    int left = matrix[i][j - 1] + 1;
                    int top = matrix[i - 1][j] + 1;
                    int both = matrix[i - 1][j - 1] + 1;
                    int temp = Math.min(left, top);
                    matrix[i][j] = Math.min(temp, both);
                }
            }
        }
        return matrix[w1.length() - 1][w2.length() - 1];
    }
}
